{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Erect the Fence II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: outerTrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #安装栅栏 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组&nbsp;<code>trees</code>，其中 <code>trees[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> 表示花园中第 <code>i</code> 棵树的坐标。</p>\n",
    "\n",
    "<p>你需要用最少的原材料给花园安装一个 <strong>圆形</strong> 的栅栏，使花园中所有的树都在被 <strong>围在栅栏内部</strong>（在栅栏边界上的树也算在内）。</p>\n",
    "\n",
    "<p>正式地说，你需要求出栅栏的圆心坐标 <code>(x,y)</code> 和半径 <code>r</code>，使花园中所有的树都在圆的内部或边界上，并且让半径 <code>r</code> <strong>最小</strong>。</p>\n",
    "\n",
    "<p>请用一个长度为 3 的数组 <code>[x,y,r]</code> 来返回圆心坐标和半径。如果答案与正确答案的误差不超过&nbsp;<code>10<sup>-5</sup></code>，则该答案将被视为正确答案通过。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/06/trees1.png\" style=\"width: 510px; height: 501px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> trees = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]\n",
    "<strong>输出:</strong> [2.00000,2.00000,2.00000]\n",
    "<strong>解释:</strong> 栅栏的圆心应当在 (2, 2) 处，半径为 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/06/trees2.png\" style=\"width: 510px; height: 501px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> trees = [[1,2],[2,2],[4,2]]\n",
    "<strong>输出:</strong> [2.50000,2.00000,1.50000]\n",
    "<strong>解释:</strong> 栅栏的圆心应当在 (2.5, 2) 处，半径为 1.5。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= trees.length &lt;= 3000</code></li>\n",
    "\t<li><code>trees[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 3000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [erect-the-fence-ii](https://leetcode.cn/problems/erect-the-fence-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [erect-the-fence-ii](https://leetcode.cn/problems/erect-the-fence-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]', '[[1,2],[2,2],[4,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[float]:\n",
    "        def cover(x, y):\n",
    "            dis = sqrt((x-x0)**2 + (y-y0)**2)\n",
    "            return dis<=r or abs(dis-r)<10**(-6)\n",
    "\n",
    "        def cal(x1, y1, x2, y2, x3, y3):\n",
    "            a, b, c, d = x1-x2, y1-y2, x1-x3, y1-y3\n",
    "            a1 = (x1*x1-x2*x2+y1*y1-y2*y2)/2\n",
    "            a2 = (x1*x1-x3*x3+y1*y1-y3*y3)/2\n",
    "            theta = b*c-a*d\n",
    "            x0 = (b*a2-d*a1)/theta\n",
    "            y0 = (c*a1-a*a2)/theta\n",
    "            return x0, y0, sqrt((x1-x0)**2+(y1-y0)**2)\n",
    "\n",
    "        random.shuffle(trees)\n",
    "        n, (x0, y0), r = len(trees), trees[0], 0\n",
    "        for i in range(1, n):\n",
    "            x1, y1 = trees[i]\n",
    "            if cover(x1, y1):\n",
    "                continue\n",
    "            (x0, y0), r = trees[i], 0\n",
    "            for j in range(i):\n",
    "                x2, y2 = trees[j]\n",
    "                if cover(x2, y2):\n",
    "                    continue\n",
    "                x0, y0, r = (x1+x2)/2, (y1+y2)/2, sqrt((x2-x1)**2+(y2-y1)**2)/2\n",
    "                for k in range(j):\n",
    "                    x3, y3 = trees[k]\n",
    "                    if cover(x3, y3):\n",
    "                        continue\n",
    "                    x0, y0, r = cal(x1, y1, x2, y2, x3, y3)\n",
    "        return [x0, y0, r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def outerTrees(self, trees: List[List[int]]) -> List[float]:\n",
    "        def cover(p):\n",
    "            return dist(p,p0)<=r+1e-6\n",
    "\n",
    "        def cal(p1, p2, p3):\n",
    "            (x1,y1),(x2,y2),(x3,y3) = p1,p2,p3\n",
    "            a, b, c, d = x1-x2, y1-y2, x1-x3, y1-y3\n",
    "            a1 = (x1*x1-x2*x2+y1*y1-y2*y2)/2\n",
    "            a2 = (x1*x1-x3*x3+y1*y1-y3*y3)/2\n",
    "            theta = b*c-a*d\n",
    "            x0 = (b*a2-d*a1)/theta\n",
    "            y0 = (c*a1-a*a2)/theta\n",
    "            p0 = [x0,y0]\n",
    "            return p0, dist(p1,p0)\n",
    "\n",
    "        T = trees\n",
    "        random.shuffle(T)\n",
    "        n, p0, r = len(T), T[0], 0\n",
    "        for i in range(1, n):\n",
    "            if cover(T[i]):\n",
    "                continue\n",
    "            p0, r = T[i], 0\n",
    "            for j in range(i):\n",
    "                if cover(T[j]):\n",
    "                    continue\n",
    "                p0, r = [(T[i][0]+T[j][0])/2, (T[i][1]+T[j][1])/2], dist(T[i],T[j])/2\n",
    "                for k in range(j):\n",
    "                    if cover(T[k]):\n",
    "                        continue\n",
    "                    p0, r = cal(T[i], T[j], T[k])\n",
    "        return [*p0, r]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
